package com.suxin.algorithm.sort;

import org.junit.jupiter.api.DynamicTest;
import org.junit.jupiter.api.Test;

/**
 * @author Tang
 * @classname Sort
 * @description [  ]
 * @date 2022/5/4 16:51
 */
public class Sort {


    private static int[] ints = new int[]{4, 9, 2, 7, 3, 4};

    /**
     * https://www.jb51.net/article/110428.htm
     * 插入排序
     * 时间复杂度：
     * 空间复杂度：
     */
    @Test
    public void insertSort() {
        for (int i = 1; i < ints.length; i++) {
            int data = ints[i];
            // 当前元素和前面排好序的元素进行对比
            int j = i - 1;
            for (; j >= 0 && data < ints[j]; j--) {
                // 前一个元素后移一位
                ints[j + 1] = ints[j];
            }
            // 赋值给要插入的位置
            ints[j + 1] = data;
        }
        printArray(ints);
    }

    /**
     * 希尔排序：缩小增量排序,分组插入排序
     * https://www.jb51.net/article/220408.htm
     * 基于插入排序的一种快速排序算法，简单插入排序只能一点点地从数组的一端一端到另一端。
     * 分组，同一个组的组内采用插入排序，不断缩小分组间隔
     * 时间复杂度：
     * 空间复杂度：
     */
    @Test
    public void hillSort() {
        // 分组
        int gap = ints.length / 2;
        while (gap > 0) {
            for (int i = gap; i < ints.length; i++) {
                int data = ints[i];
                // 同组中的后一个要比较的数
                int index = i - gap;
                while (index >= 0 && data < ints[index]) {
                    // 同一个组中的后一个赋值给前一个
                    ints[index + gap] = ints[index];
                    // 同组中的下一个需要对比的位置
                    index -= gap;
                }
                // 赋值
                ints[index + gap] = data;
            }
            gap = gap / 2;
        }
        printArray(ints);
    }

    /**
     * 归并排序: 分治思想
     * 划分的时间复杂度为o(log2(n))，合并的时间复杂度为o(n)，所以时间复杂度为o(n*log2(n))
     * 合并时有用到辅助表，故空间复杂度为o(n)。
     */
    @Test
    public static void mergeSort(int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 分
            mergeSort(left, mid);
            mergeSort(mid + 1, right);
            // 治
            merge(mid, left, right);
        }
    }

    public static void merge(int mid, int left, int right) {
        // 这个数组用来存放这个范围内有序的数据
        int[] temp = new int[ints.length];
        int local = left;
        // [point1,mid] 区间的有序数 区间1
        int point1 = left;
        // [mid+1,right] 区间的有序数 区间2
        int point2 = mid + 1;

        // 让有序区间2 往有序区间1 里面插入

        // 左边是有序的部分，，只需要排序右边的部分
        while (point1 <= mid && point2 <= right) {
            // 区间1 的元素 < 区间2 的元素
            if (ints[point1] < ints[point2]) {
                // 区间1的元素放到 temp 数组的 point1 的位置
                // 有序的数据最终都排到 temp数组里面
                temp[local] = ints[point1];
                // 后移区间1指针拿下一个数字比较
                point1++;
            } else {
                // 区间1 的元素 > 区间2 的元素
                // 区间2的元素放到 temp 数组的 point2 的位置
                temp[local] = ints[point2];
                // 后移区间2指针拿下一个数字比较
                point2++;
            }
            local++;
        }
        // 其他部分的元素直接添加到数组
        // 上面执行完，必定有个区间point指针没有走完，另外一个区间是已经走完的，
        // 因为上面2个区间都是有序区间，两个有序区间进行比较


        // point1区间没有走完， point1区间里面的值都是最大值
        while (point1 <= mid) {
            temp[local++] = ints[point1++];
        }

        // point2区间没有走完， point2区间里面的值都是最大值
        while (point2 <= right) {
            temp[local++] = ints[point2++];
        }

        // 上面执行完temp数组里面就会是一个顺序区间
        // 将顺序区间添加到原数组里面
        for (int i = left; i <= right; i++) {
            ints[i] = temp[i];
        }
    }

    /**
     * 选择排序
     */
    @Test
    public static void selectSort() {
        for (int i = 0; i < ints.length; i++) {
            int index = i;
            // 找到最小的数下标
            for (int j = i + 1; j < ints.length; j++) {
                if (ints[index] >= ints[j]) {
                    index = j;
                }
            }
            // 交换数据 ints[index]是最小的数
            int temp = ints[index];
            // 当前位置 和 最小的数位置进行交换
            ints[index] = ints[i];
            ints[i] = temp;
        }
    }


    /**
     * 冒泡排序
     * 元素互相比较，小的话，就直接交换位置
     * 冒泡：会把每轮最大的数冒泡到最后面
     */
    public static void bubblingSort() {
        //临时变量
        int temp;
        //每一轮比较过后,都会得到一个最大值
        for (int i = 0; i < ints.length - 1; i++) {
            // ints.length - 1 - i 最后面的是已经排完序的
            for (int j = 0; j < ints.length - 1 - i; j++) {
                //判断后一个数组元素跟前一个数组元素值的大小
                //如果后一个元素的小于前一个数组的值，就互换位置
                if (ints[j + 1] > ints[j]) {
                    temp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 快速排序
     * 优化点: 基数的选择
     * @param left left
     * @param right right
     */
    public static void quickSort(int left,int right) {
        // 循环跳出条件
        if (left > right) {
            return;
        }
        // 基数
        int baseData = ints[left];
        int l = left;
        int r = right;
        //这层循环的目的就是 改变序列为 以基数为中心的，左小 右大 的新序列
        while (l < r) {
            //1.先从后向前 找到小于基数的
            while (l < r && ints[r] >= baseData) {
                r--;
            }
            //2.从前往后 找到大于基数的
            while (l < r && ints[l] <= baseData) {
                l++;
            }
            //3.交换数值
            if (l < r) {
                int temp = ints[r];
                ints[r] = ints[l];
                ints[l] = temp;
            }
        }
        //  交换基准数
        ints[left] = ints[l];
        ints[l] = baseData;
        //  左右两边分别排序
        quickSort(left,l - 1);
        quickSort(l + 1,right);
    }

    public static void main(String[] args) {
//        mergeSort(0,ints.length - 1);
//        selectSort();
//        bubblingSort();
        quickSort(0, ints.length - 1);
        printArray(ints);
    }

    private static void printArray(int[] source) {
        for (int j : source) {
            System.out.print("\t" + j);
        }
        System.out.println();
    }

}